package Leetcode.StackAndQueue.trapWater42;

/**
 * 暴力解法 对于每一列求每一列能装到的水的体积
 * 该体积由左右边界决定  根据木桶效应 则为左右边界的最小值减去自身的体积
 * 所以遍历数组 对每一列遍历找左右边界
 * 该方法时间复杂度 O(n^2) 空间复杂度O(1)
 */
public class Solution {
    public int trap(int[] height) {
        int ans = 0;
        int size = height.length;
        for (int i = 1; i < size - 1; i++) {
            int max_left = 0, max_right = 0;
            for (int j = i; j >= 0; j--) {
                //Search the left part for max bar size
                max_left = Math.max(max_left, height[j]);
            }
            for (int j = i; j < size; j++) {
                //Search the right part for max bar size
                max_right = Math.max(max_right, height[j]);
            }
            ans += Math.min(max_left, max_right) - height[i];
        }
        return ans;

    }

    public static void main(String[] args) {
        int[] nums = {0,1,0,2,1,0,1,3,2,1,2,1};
        Solution solution = new Solution();
        System.out.println(solution.trap(nums));
    }
}
